package weekthree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class SurroundedRegions_130 {
    private int[] dx = {1, 0, -1, 0};
    private int[] dy = {0, 1, 0, -1};
    private boolean[][] visit;
    private int m, n;
    private List<List<int[]>> insideO;

    //去掉最外围一圈，然后bfs，记录访问过的'O'，需要边界检查
    //1， 如果是'O',而且不在边界上，入队
    //2, 如果是'O'，但是在边界上，说明这组dfs遍历的结果失效。
    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        visit = new boolean[m][n];
        insideO = new ArrayList<>();

        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (!visit[i][j] && board[i][j] == 'O')
                    bfs(board, i, j);
            }
        }
        for (List<int[]> list : insideO) {
            for (int[] index : list) {
                board[index[0]][index[1]] = 'X';
            }
        }

    }

    private void bfs(char[][] board, int x, int y) {
        boolean hasSide = false;
        Queue<int[]> queue = new LinkedList<>();
        visit[x][y] = true;
        List<int[]> hasPassed = new ArrayList<>();
        queue.offer(new int[]{x, y});
        hasPassed.add(new int[]{x, y});
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nextx = curr[0] + dx[i];
                int nexty = curr[1] + dy[i];
                if (!visit[nextx][nexty] && board[nextx][nexty] == 'O' && nextx != 0 && nextx != m - 1 && nexty != 0 && nexty != n - 1) {
                    queue.offer(new int[]{nextx, nexty});
                    visit[nextx][nexty] = true;
                    hasPassed.add(new int[]{nextx, nexty});
                } else if (board[nextx][nexty] == 'O' && (nextx == 0 || nextx == m - 1 || nexty == 0 || nexty == n - 1)) {
                    hasSide = true;
                }
            }
        }
        if (!hasSide) insideO.add(hasPassed);
    }
}
